# 236.二叉树的最近公共祖先
# 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
# 百度百科中最近公共祖先的定义为：“对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能
# 大（一个节点也可以是它自己的祖先）。”
#
# 示例1：
# 输入：root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
# 输出：3
# 解释：节点5和节点1的最近公共祖先是节点3 。
#
# 示例2：
# 输入：root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
# 输出：5
# 解释：节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。
#
# 示例3：
# 输入：root = [1, 2], p = 1, q = 2
# 输出：1


class TreeNode:
    def __init__(self, x,left=None,right=None):
        self.val = x
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 没太明白，迷迷糊糊的
        # 1.确定参数和返回值
        def traver(root,p,q)->'TreeNode':
            if not root:
                return
            if root == p or root == q:
                return root
            left = traver(root.left, p, q)
            right = traver(root.right, p, q)
            if left and right:
                return root
            if not left and right:
                return right
            if left and not right:
                return left
            if not left and not right:
                return
        return traver(root,p,q)

if __name__ == '__main__':
    #      4
    #   2      7
    # 1   3
    a31 = TreeNode(1)
    a32 = TreeNode(3)
    a21 = TreeNode(2,a31,a32)
    a22 = TreeNode(7)
    a11 = TreeNode(4,a21,a22)
    tmp = Solution()
    res1 = tmp.lowestCommonAncestor(a11,a31,a22)
    print(res1.val)
